package main

import (
	"fmt"
)

/**
执行用时：116 ms, 在所有 Go 提交中击败了53.38%的用户
内存消耗：9.4 MB, 在所有 Go 提交中击败了42.29%的用户
 */
func maxProfit(prices []int) int {

	n := len(prices)
	f := make([]int, n + 1)
	for i, minp := 1, int(1e9); i <= n; i++ {
		f[i] = max(f[i - 1], prices[i - 1] - minp)
		minp = min(minp, prices[i - 1])
	}

	res := 0
	for i, maxp := n, 0; i > 0; i-- {
		res = max(res, maxp - prices[i - 1] + f[i - 1])
		maxp = max(maxp, prices[i - 1])
	}
	return res
}

// 求最大值
func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// 求最小值
func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	prices := []int{1, 2, 3, 4, 5}
	fmt.Println(maxProfit(prices))  // 4
}
